這是什麼？

Graph 內，針對有向圖的節點，進行 Linear Sort。
執行前有一點要遵守：如果該節點有個指向自己的節點，將視為執行該節點的條件，因此要執行順序優於該節點。

想像有一個向量圖長這樣子：

首先，標上每個節點指向自己的數量。

接著找尋標示數量為 0 的節點，如圖所示，此時只有 1。將其移除（表示已執行）。

此時，重新計算指向自己的數量，發現有兩個數量為 0 的節點：0 & 2，此時移除這兩個都可以，這邊移除 0。

重複上面步驟，重新計算、找出為 0 的節點，此時只有 2，將其移除。

重新計算後，目前有兩個為 0：4 & 5，接著移除 4。

再來移除 5。

最後剩下 3。

因此，依照移除的順序排序：

1 -> 0 -> 2 -> 4 -> 5 -> 3

剛剛有同時出現多組 0，每個節點都可以選擇並產生分歧。因此，Topological Sort 要列出所有可能：

1 -> 0 -> 2 -> 4 -> 5 -> 3
1 -> 0 -> 2 -> 5 -> 4 -> 3
1 -> 2 -> 0 -> 4 -> 5 -> 3
1 -> 2 -> 0 -> 5 -> 4 -> 3
1 -> 2 -> 5 -> 0 -> 4 -> 3

來源

刷題：207. Course Schedule

題目

There are a total of numCourses courses you have to take, labeled from 0 to numCourses-1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

Example 1:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses to take.
             To take course 1 you should have finished course 0. So it is possible.

Example 2:

Input: numCourses = 2, prerequisites = [[1,0],[0,1]]
Output: false
Explanation: There are a total of 2 courses to take.
             To take course 1 you should have finished course 0, and to take course 0 you should
             also have finished course 1. So it is impossible.

Constraints:

• The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.
• You may assume that there are no duplicate edges in the input prerequisites.
• 1 <= numCourses <= 10^5

思考

給予課堂總數，列出哪些課有先修課，接著排出修課順序。很明顯，是 Topological Sort 的應用題：

• 課堂總數等於節點。
• 先修課等於該節點被哪些節點指著。

最後，如果排列的結果，其節點數量等於課堂數量，表示所有課程都有排到，則回傳 True，反之，回傳 False。

解題

JS

/**
 * @param {number} numCourses
 * @param {number[][]} prerequisites
 * @return {boolean}
 */
const canFinish = (numCourses, prerequisites) => {
  /**
   * 標註該節點指向的數量
   * @type {number[]}
   */
  let nodeWithPointToArray = new Array(numCourses);
  nodeWithPointToArray.fill(0);
  /**
   * 標註該節點被哪些節點指向
   * @type {number[][]}
   */
  let bePointedNodeArray = new Array(numCourses);
  bePointedNodeArray.fill([]);
  /**
   * 標註先決條件較多的節點
   * @type {number[]}
   */
  let finishedNodeArray = [];

  prerequisites.forEach((coursePair) => {
    nodeWithPointToArray[coursePair[0]]++;
    bePointedNodeArray[coursePair[1]] = bePointedNodeArray[coursePair[1]].concat(coursePair[0]);
  });

  for (let i = 0; i < numCourses; i++) {
    if (nodeWithPointToArray[i] === 0) {
      finishedNodeArray = finishedNodeArray.concat(i);
    }
  }

  for (let i = 0; i !== finishedNodeArray.length; i++) {
    let course = finishedNodeArray[i];
    let coursePrerequisite = bePointedNodeArray[course];

    coursePrerequisite.forEach((prerequisite) => {
      nodeWithPointToArray[prerequisite]--;

      if (nodeWithPointToArray[prerequisite] === 0) {
        finishedNodeArray = finishedNodeArray.concat(prerequisite);
      }
    });
  }

  return finishedNodeArray.length === numCourses;
};

Java

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (prerequisites == null || prerequisites.length == 0) {
            return true;
        }

        HashMap<Integer, List<Integer>> graph = new HashMap<>();
        int[] predecessors = new int[numCourses];

        for (int i = 0; i < prerequisites.length; i++) {
            int[] coursePair = prerequisites[i];
            int endCourse = coursePair[0];
            int startCourse = coursePair[1];

            if (graph.get(startCourse) == null) {
                graph.put(startCourse, new ArrayList<Integer>());
            }

            graph.get(startCourse).add(endCourse);
            predecessors[endCourse]++;
        }

        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < predecessors.length; i++) {
            if (predecessors[i] == 0) {
                queue.add(i);
            }
        }

        while (!queue.isEmpty()) {
            int currentCourse = queue.poll();
            List<Integer> successors = graph.get(currentCourse);

            if (successors == null) {
                continue;
            }

            for (Integer vertex : successors) {
                predecessors[vertex]--;

                if (predecessors[vertex] == 0) {
                    queue.add(vertex);
                }
            }
        }

        for (int i = 0; i < predecessors.length; i++) {
            if (predecessors[i] != 0) {
                return false;
            }
        }

        return true;
    }
}

C

struct adj_node
{
    int depth;
    struct adj_node *next;
};

struct adj_list
{
    struct adj_node *head;
};

struct Graph
{
    int vertex;
    struct adj_list *arr;
};

struct Graph *create_graph(int num)
{
    struct Graph *graph = (struct Graph *)malloc(sizeof(struct Graph));
    graph->vertex = num;
    graph->arr = (struct adj_list *)malloc(sizeof(struct adj_list) * num);

    for (int i = 0; i < num; i++)
    {
        graph->arr[i].head = NULL;
    }

    return graph;
}

void add_edge(struct Graph *graph, int src, int dest)
{
    struct adj_node *new_node = (struct adj_node *)malloc(sizeof(struct adj_node));
    new_node->depth = dest;
    new_node->next = graph->arr[src].head;
    graph->arr[src].head = new_node;
}

bool is_cyclic(struct Graph *graph, bool *visited, bool *re_stack, int index)
{
    if (visited[index] == false)
    {
        visited[index] = true;
        re_stack[index] = true;
        struct adj_node *current_node = graph->arr[index].head;

        while (current_node)
        {
            if (!visited[current_node->depth] && is_cyclic(graph, visited, re_stack, current_node->depth))
            {
                return true;
            }
            else if (re_stack[current_node->depth] == true)
            {
                return true;
            }

            current_node = current_node->next;
        }
    }

    re_stack[index] = false;
    return false;
}

bool canFinish(int numCourses, int **prerequisites, int prerequisitesSize, int *prerequisitesColSize)
{
    struct Graph *graph = create_graph(numCourses);
    int i = 0;

    for (i = 0; i < prerequisitesSize; i++)
    {
        add_edge(graph, prerequisites[i][0], prerequisites[i][1]);
    }

    bool visited[numCourses];
    bool re_stack[numCourses];

    for (i = 0; i < numCourses; i++)
    {
        visited[i] = false;
        re_stack[i] = false;
    }

    for (i = 0; i < numCourses; i++)
    {
        if (is_cyclic(graph, &visited[0], &re_stack[0], i))
        {
            return false;
        }
    }

    return true;
}

看法

這邊的做法是建立三個陣列，負責表示 該節點指向其他節點的數量、該節點被誰指著 以及 先決條件較多的。重頭戲在排列 finishedNodeArray，從先決條件較多的節點開始，找尋指向該節點的節點，然後將其指向數量減一，判斷是不是為零。如果為零，表示該節點的指向其他節點的數量較少，同時表示先決條件較多。將為零的節點放入 finishedNodeArray 內。

不得不承認，將腦中觀念如何轉換為程式碼，尤其在不熟悉的做法上，依舊是個挑戰。

隔天了解如何實作 Java & C 時，才注意到不少 Submission 建立兩個建立來判斷該節點的狀態，此外，還要判斷 Graph 是不是循環（cyclic），避免陷入無限循環內。

Graph 這水真深啊！

結論

Topological Sort 有不少應用，也是 Graph 在面試上容易出現的考題。即使懂相關概念，沒有多寫點題目增加反應速度，在面試時也是容易被刷掉。

隔天發現不少人會使用 DFS 來處理這題，之後來研究一下相關步驟。